29缓存一致性 I
AP SHANTHI博士
本模块的目标是讨论多处理器中的缓存一致性问题，并详细阐述基于窥探的缓存一致性协议。
在上一个模块中，我们指出了与多处理器相关的挑战。
我们指出的两个主要挑战如下：
1. 程序的并行和顺序部分
• 我们的程序将同时具有顺序代码和并行代码。随着顺序代码的增加，多处理器的性能将会下降。因此，我们需要编写能够利用底层并行架构的全部功能的并行程序。
2. 通信延迟
• 处理器之间的通信延迟将是一个主要的开销，必须减少。这可以通过在多个处理器中缓存数据来完成。缓存用于增加带宽和减少访问延迟，对私有数据和共享数据都很有用。
但是，当我们在多个处理器中缓存数据时，就会出现缓存一致性和一致性的问题。我们将在本模块和下一个模块中详细说明。
多处理器缓存一致性：对称共享内存机器通常支持共享和私有数据的缓存。私有数据由单个处理器使用，而共享数据由多个处理器使用，本质上通过共享数据的读取和写入在处理器之间提供通信。当私有数据被缓存时，它的位置被迁移到缓存中，减少了平均访问时间以及所需的内存带宽。由于没有其他处理器使用这些数据，因此程序行为与单处理器中的行为相同。同样，当共享数据被缓存时，共享值可能会被复制到多个缓存中。除了减少访问延迟和所需的内存带宽之外，这种复制还减少了多个处理器同时读取的共享数据项可能存在的争用。然而，共享数据的缓存引入了缓存一致性问题。这是因为共享数据在不同的缓存中可能具有不同的值，因此必须进行适当的处理。图 33.1 说明了这个问题。我们可以看到，处理器 A 和 B 都将位置 X 读取为 1。稍后，当处理器 A 将其修改为值 0 时，处理器 B 仍然将其作为值 1。因此，两个不同的处理器可以对同一位置具有两个不同的值. 这种困难通常被称为缓存一致性 问题。
非正式地，如果对数据项的任何读取返回该数据项的最近写入值，我们可以说内存系统是一致的。这个简单的定义包含内存系统行为的两个不同方面，这两个方面对于编写正确的共享内存程序都至关重要。第一个方面称为一致性，定义读取可以返回哪些值。第二个方面称为一致性，它确定读取何时返回写入值。
如果以下条件成立，则记忆系统是连贯的：
1. 处理器 P 对位置 X 的读取，在 P 对 X 的写入之后，在 P 写入和读取之间没有发生另一个处理器对 X 的写入，总是返回 P 写入的值。
2. 如果读和写在时间上充分分离并且在两次访问之间没有发生对 X 的其他写操作，则处理器对位置 X 的读操作会在另一个处理器对 X 的写操作之后返回写入值。
3.对同一位置的写入被序列化；也就是说，任何两个处理器对同一位置的两次写入对于所有处理器都是以相同的顺序看到的。这确保我们不会在新值之后看到旧值。
第一个属性只是保留程序顺序，即使在单处理器中也是如此。第二个属性定义了拥有一致的内存视图意味着什么的概念。第三个属性确保以正确的顺序看到写入。
尽管刚刚描述的三个属性足以确保连贯性，但何时看到写入值的问题也很重要。我们不能期望 X 的读取立即看到其他处理器为 X 写入的值。例如，如果在一个处理器上写入 X 在另一个处理器上读取 X 之前的时间很短，则可能无法确保读取返回写入的数据的值，因为写入的数据甚至可能不那时已经离开了处理器。读取器必须看到写入值的确切时间问题由内存一致性模型定义 ，这将在后面的模块中讨论。连贯性和一致性是互补的：连贯性定义了对同一内存位置的读写行为，而一致性则定义了相对于访问其他内存位置的读写行为。
缓存一致性协议：多处理器支持迁移的概念，其中数据被迁移到本地缓存和复制，其中相同的数据被复制到多个缓存中。缓存一致性协议通过迁移和复制确保数据的一致性视图。实现缓存一致性协议的关键是跟踪任何数据块共享的状态。有两类协议，它们使用不同的技术来跟踪共享状态：
1. 基于目录：一块物理内存的共享状态只保存在一个位置，称为目录。还可以分发目录以提高可伸缩性。通信是通过互连网络使用点对点请求建立的。
2. Snoop based：每个缓存有一个物理内存块的数据副本，也有一个该块共享状态的副本，但不保持集中状态。缓存都可以通过某种广播介质（总线或交换机）访问，并且所有缓存控制器监视或窥探介质以确定它们是否具有在总线或交换机访问上请求的块的副本。需要广播，因为缓存信息在处理器中 适用于小型机器（大部分市场）
在本模块中，我们将重点介绍基于窥探的方法。
史努比缓存一致性协议：有两种方法可以保持一致性要求。一种方法是确保处理器在写入数据项之前对其具有独占访问权限。这种类型的协议称为写入无效协议，因为它会使写入时的其他副本无效。它是最常见的协议，用于侦听和目录方案。独占访问可确保在写入时不存在某个项目的其他可读或可写副本：该项目的所有其他缓存副本都将失效。
写无效的替代方案是写广播或写更新机制。在这里，所有缓存的副本同时更新。这需要更多的带宽。此外，当同一位置发生多次更新时，会进行不必要的更新。但是，写入和读取之间的延迟较低。在接下来的讨论中，我们将假设写无效方法。
总线通常用于执行无效。为了执行无效，处理器简单地获取总线访问权并在总线上广播要无效的地址。所有处理器都在总线上不断地窥探，观察地址。处理器检查总线上的地址是否在它们的缓存中。如果是，则缓存中的相应数据无效。当发生对共享块的写入时，写入处理器必须获得总线访问权以广播其无效。如果两个处理器同时尝试写入共享块，则当它们为总线进行仲裁时，它们广播无效操作的尝试将被串行化。第一个获得总线访问权的处理器将导致它正在写入的块的任何其他副本无效。如果处理器试图写入同一个块，
Also, we need to locate a data item when a cache miss occurs. In a write-through cache, it is easy to find the recent value of a data item, since all written data are always sent to the memory, from which the most recent value of a data item can always be fetched. For a write-back cache, the most recent value of a data item can be in a cache rather than in memory. The snooping process is used here also. All processors snoop on the address placed on the bus. If a processor finds that it has a dirty copy of the requested cache block, it provides that cache block in response to the read request and causes the memory access to be aborted. In this module, we will examine the implementation of coherence with write-back caches.
The tag bits, the dirty bit and the valid bit that we discussed with respect to caches are used here also. The normal cache tags can be used to implement the process of snooping, the dirty bit to indicate whether the cache block was modified and the valid bit to indicate the validity of the cache block. The only other additional bit that is needed is to indicate whether or not a cache block is shared. For this, we can add an extra state bit associated with each cache block, indicating whether the block is shared. When a write to a block in the shared state occurs, the cache generates an invalidation on the bus and marks the block as exclusive. No further invalidations will be sent by that processor for that block. The processor with the sole copy of a cache block is normally called the owner of the cache block.
When an invalidation is sent, the state of the owner’s cache block is changed from shared to unshared (or exclusive). If another processor later requests this cache block, the state must be made shared again. Since our snooping cache also sees any misses, it knows when the exclusive cache block has been requested by another processor and the state should be made shared.
每个总线事务都必须检查缓存地址标签，这可能会干扰处理器缓存访问。减少这种干扰的一种方法是复制标签。通过将监听请求定向到 L2 缓存，处理器也可以减少多级缓存中的干扰，处理器仅在 L1 缓存未命中时使用。要使此方案起作用，L1 缓存中的每个条目都必须存在于 L2 缓存中，该属性称为包含属性。如果侦听在 L2 缓存中获得命中，则它必须为 L1 缓存进行仲裁以更新状态并可能检索数据，这通常需要处理器停顿。
一个示例史努比协议——MSI：我们将看一个示例 MSI 协议，然后检查这个基本协议的扩展。在这种情况下，缓存块可以处于三种状态——修改（M）、共享（S）和无效（I）。每个内存块都处于一种状态：
– 清理所有缓存并更新内存（共享）
– 或仅在一个缓存中脏（独占/修改）
– 或不在任何缓存中（无效）
– 共享：块可以被读取
– 或独占：缓存只有副本、可写和脏
– 或无效：块不包含数据
对干净行的写入被视为未命中。
侦听一致性协议通常通过在每个节点中包含一个有限状态控制器来实现。该控制器响应来自处理器和总线的请求，更改所选缓存块的状态，以及使用总线访问数据或使其无效。
图 33.2 显示了节点中处理器缓存模块生成的请求（在表格的上半部分）以及来自总线的请求（在表格的下半部分）。各项活动详述如下：
1. 处理器的读请求是命中——缓存块可以处于共享状态或修改状态——从本地缓存读取数据的正常命中操作。
2. 处理器读取请求，未命中。这表明缓存块可以处于以下三种状态中的任何一种：
a. Invalid – It is a normal miss and the read request is placed on the bus. The requested block will be brought from memory and the status will become shared.
b. Shared – It is a replacement miss, probably because of an address conflict. The read request is placed on the bus and the requested block will be brought from memory and the status will become shared.
c. Modified – It is a replacement miss, probably because of an address conflict. The read request is placed on the bus, the processor -cache holding it in the modified state writes it back to memory and the requested block will be brought from memory and the status will become shared in both the caches.
3. Write request by the processor which is a hit – the cache block can be in the shared state or modified state.
a. Modified – Normal hit operation where the data is written in the local cache.
湾 共享——这是一个连贯的行动。块的状态必须更改为已修改，因此称为升级或所有权未命中。必须在总线上发送 Invalidates 以使共享状态中的所有其他副本无效。
4. 处理器写请求，未命中。这表明缓存块可以处于以下三种状态中的任何一种：
一个。无效——这是一个正常的未命中，写请求被放置在总线上。请求的块将从内存中取出，状态将变为已修改。
湾 共享 - 这是一个替换未命中，可能是因为地址冲突。写请求被放置在总线上，被请求的块将从内存中取出，状态将被修改。其他共享副本将失效。
C。修改 - 这是一个替换未命中，可能是因为地址冲突。写请求被放置在总线上，处理器缓存将它保持在修改状态，将它写回内存，无效，请求的块将从内存中取出，状态将在写缓存中修改。
5. 从总线端，可以抛出一个读未命中，并且缓存块可以处于共享状态或修改状态
一个。共享 - 保存处于共享状态的数据的缓存之一或内存将通过发送块来响应未命中
湾 修改 - 必须进行一致性操作。块必须提供给请求缓存，并且块在两个缓存中的状态是共享的。
6. 当共享块的写请求到来时，总线发送无效。共享块必须无效，这是一个一致性操作。
7. 从总线端，可以抛出写未命中，缓存块可以处于共享状态或修改状态
一个。共享 - 这是对共享块的写入请求。因此，该块必须无效，这是一个一致性操作。
湾 修改 - 必须进行一致性操作。该块必须被写回，并且它的状态必须在原始缓存中无效。
图 33.3 显示了使用写无效协议和回写缓存的单个缓存块的有限状态转换图。为简单起见，协议的三个状态被复制以表示基于处理器请求的转换（左侧，对应于图 33.2 中表格的上半部分），而不是 基于总线请求的转换（右侧，这对应于图 33.2 中表格的下半部分）。每个节点中的状态代表处理器或总线请求指定的所选缓存块的状态。图 33.3 提供了一个组合视图。
实现的复杂性：虽然协议讨论看起来很简单，但在实现中存在许多复杂性。最重要的问题是协议假设操作是原子的——也就是说，一个操作可以以不会发生干预操作的方式完成。例如，所描述的协议假设可以检测写入未命中、获取总线并作为单个原子操作接收响应。事实上，这不是真的。类似地，如果我们像所有最近的多处理器一样使用开关，那么即使读取未命中也不是原子的。非原子操作引入了协议死锁的可能性，这意味着它达到了无法继续的状态。
对称共享内存多处理器和侦听协议的局限性：随着多处理器中处理器数量的增加，或随着每个处理器的内存需求的增加，系统中的任何集中资源都可能成为瓶颈。在基于总线的多处理器的简单情况下，总线和内存成为瓶颈。因此，可扩展性成为一个问题。为了增加处理器和内存之间的通信带宽，设计人员使用了多条总线以及互连网络，例如交叉开关或小型点对点网络。在这样的设计中，内存系统可以配置为多个物理bank，从而在保持对内存的统一访问时间的同时提高有效内存带宽。
扩展到MSI协议：基本MSI协议由以提供优化添加其他状态延长。
1. 第一个扩展是添加一个独占状态，MESI（Modified, Exclusive, Shared and Invalid）协议。添加独占状态以指示仅在一个缓存中的干净块。这可以防止需要在写入时发送写入无效，因为该块仅在一个缓存中可用。处理器只是将状态更改为已修改。但是，当发生 E 状态块的读取未命中时，状态必须从独占变为共享，以保持一致性。
2. Intel i7 使用的另一个扩展是在 MESI 协议中添加一个额外的状态，称为转发状态，导致MESIF协议。这标识了一个共享缓存，当有请求时，它将转发数据块。当一个缓存块被多个缓存共享，并且还有一个读未命中时，内存可以提供该块，或者其中一个缓存可以提供数据。缓存块，被指定为转发块，负责转发数据。这避免了在提供数据时各种缓存之间的争用。此外，为了确保转发缓存不会替换该块，转发状态被授予最近获取该块的缓存。
3. 另一个扩展是添加一个拥有状态，指示缓存是块的所有者，并且在内存中不是最新的。这是MOESI协议。通常，当处于修改状态的块被共享时，这两个块的状态将被共享，并且该块将被写回内存。但是，在 MOESI 协议中，原始缓存的状态由已修改变为已拥有，表示该内存没有副本，只有该缓存有更新的副本。该缓存还负责在未命中时提供数据。当块被替换时，它将把它写回内存。AMD Opteron 使用 MOESI 协议。
总而言之，我们已经定义了多处理器中的缓存一致性问题。我们已经定义了两种类型的缓存一致性协议。已经详细讨论了基于窥探的缓存一致性协议。已经讨论了基本协议的实现问题、限制和扩展。
网页链接/支持材料
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A.Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。